package bintree.leetcode;

/**
 * 最近公共祖先
 * @author yuisama
 * @date 2022/05/15 09:48
 **/
public class Num236_LCA {
    // 最近公共祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 从树中每个节点开始遍历找p和q这两个节点
        findNode(root,p,q);
        return lca;
    }

    /**
     * 从当前以root为树根的结点开始出发，能否找到p或者q，找到一个就return true
     * @param root
     * @param p
     * @param q
     */
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        // 返回1说明，此时从左子树中至少找到了一个节点
        int left = findNode(root.left,p,q) ? 1 : 0;
        // 返回1说明在右子树中也至少找到了节点
        int right = findNode(root.right,p,q) ? 1 : 0;
        // 当前树根就是p或者q的其中一个
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid  == 2) {
            // 此时p和q出现在以root为根的两个位置，这个root一定是lca!!!
            lca = root;
        }
        // 大于0，说明至少找到一个节点
        return (left + right + mid) > 0;
    }
}